00100	ROBOTS
00200	
00300	
00400	by John McCarthy,
00500	
00600	[John  McCarthy  is Professor of Computer Science and Director of the
00700	Artificial Intelligence Laboratory,  Stanford  University,  Stanford,
00800	California]
00900	
01000		The   robot   or  artificial  human  has  been  portrayed  in
01100	literature especially in science fiction, for several hundred  years.
01200	Only   in  the  last  twenty-five  years,  however,  has  there  been
01300	scientific work directly aimed at making a machine that can  perceive
01400	objects  and  events in the physical world like a human and which can
01500	behave intelligently on the basis of what it perceives.
01600	
01700		The scientific event  that  made  research  on  robotics  and
01800	artificial  intelligence  possible  was the development of the stored
01900	program digital computer.   While the  idea  of  the  stored  program
02000	computer goes back to the English scientist Charles Babbage 100 years
02100	ago, the first practical computers were put into operation  in  1949.
02200	They  were  too slow, had too little memory, were too unreliable, and
02300	too hard to program for serious work in artificial intelligence,  but
02400	their  very  existence  and the assurance that these defects would be
02500	relieved set people's thoughts going in new directions.
02600	
02700		First of all, it became clear that the hard problem would not
02800	be   the  physical  construction  of  robots  or  even  the  physical
02900	construction of the computer that would serve as the  robot's  brain.
03000	Instead,  the  hard problem would be inventing the procedures (called
03100	programs) that the machine would have to carry out in order to behave
03200	intelligently  in  the  wide  variety  of  circumstances  that humans
03300	encounter and handle routinely. Here are some of  the  problems  that
03400	have to be solved:
03500	
03600	WHAT ARE THE PROBLEMS OF ROBOTICS?
03700	
03800		1.     What are the facts that a human knows and a robot must
03900	know about a situation in order to decide what to do?  How can  these
04000	facts be represented in the memory of a computer?
04100	
04200		2.   What are the general facts about the world that enable a
04300	human to determine in a particular  situation  what  are  the  likely
04400	results of the different actions he might undertake?
04500	
04600		3.    What are the purposes that humans have or that we might
04700	wish a robot to have, and how can these be represented in a computer?
04800	This includes restrictions we would like robots to observe.
04900	
05000		4.   How should the machine decide what to do on the basis of
05100	the  information  it  has  about  the   particular   situation,   its
05200	information about the world in general, its information about its own
05300	capabilities including its ability to get  further  information,  and
05400	its information about its own purposes?
05500	
05600		5.    How can we be sure that intelligent robots, once we get
05700	them, will behave nicely, and won't get  notions  of  conquering  the
05800	world either for themselves or for people that might like to do that?
05900	
06000		6.     How is the robot to obtain information about the world
06100	from the senses with which we equip it?  It  is  easy  to  connect  a
06200	television  camera  to  a  computer  so that a picture comes in as an
06300	array of light intensity and color values, but it  is  very  hard  to
06400	program  the  computer  to  find the people in the picture and decide
06500	what they are doing.
06600	
06700		None of the above problems has been solved, but a  start  has
06800	been  made  on  all  of them, and systems have been built that behave
06900	properly in very limited circumstances.
07000	
07100	
07200	WHAT HAS BEEN ACCOMPLISHED
07300	
07400		When  someone  claims  to  have  made a computer program that
07500	behaves intelligently, the first question someone else will  ask  is,
07600	"how  smart  is  it compared to people".  Therefore, one of the first
07700	tasks people tried to program is playing games, and the first game to
07800	be discussed was the game of chess.
07900	
08000		One  of  the  first  efforts to program chess was made by the
08100	British scientist Alan Turing.   He did this before  he  even  had  a
08200	computer  to work with, by carefully writing down the rules he wanted
08300	the computer to follow, and then carrying out the rules by hand.  His
08400	idea  was to provide a rule for evaluating a position: so many points
08500	for each kind of piece posessed by each  side,  so  many  points  for
08600	mobility of one's forces which he proposed to measure in terms of the
08700	number of legal moves, so many points for control of  center  squares
08800	which  is  important in chess, points for control of the squares near
08900	the kings, and points based on the structure formed  by  each  side's
09000	pawns,  and  perhaps a few more criteria.  The program would evaluate
09100	the number of points of each possible move and choose the  move  that
09200	had  the  most  points.    Turing knew that this program for choosing
09300	moves would not play  expert  chess,  but  he  hoped  it  would  play
09400	passsable  beginner's chess.  His non computer experiments led him to
09500	conclude that the program would do so, but we cannot be  sure,  since
09600	the  program  was  not  run  on a computer, and hand simulations have
09700	since proved to err on the optimistic side. When someone carries  out
09800	a  set  of  rules for playing a game, it is very difficult for him to
09900	avoid applying some common sense of his own.
10000	
10100		Since that time, a number of chess programs have been written
10200	that play fairly well.  One of them, written by Richard Greenblatt of
10300	Massachusetts Institute of Technology won the class  D  trophy  in  a
10400	tournament with human players.  This gave it a rating of class C. All
10500	these  programs  use  extensions  and  elaborations  of  the  program
10600	proposed  by Turing.  In order to understand some of the ideas behind
10700	these improvements, let us consider a diagram of the  possible  moves
10800	available  to  the two players.  This diagram is called the move tree
10900	of the game.
11000	
11100	
11200		Figure 1.
11300	
11400		In  the  initial  position, we show two possible moves by the
11500	program. These may not be all the moves that  are  available  -  just
11600	those that some process we have not yet specified considers worthy of
11700	serious consideration. The first of these moves leads to  a  position
11800	in  which  the program's opponent has two moves, and the second leads
11900	to a position with three moves.  As shown in the diagram each of  the
12000	first  two  moves  considered for the opponent leads to a position in
12100	which there are three moves for the program.   Beyond  the  positions
12200	shown,  there  may  be  additional  moves  for  the  machine  and its
12300	opponent, but let us suppose that the investigation  is  not  carried
12400	further because the program has some criteria that tell it that these
12500	end positions are sufficiently static so that they can  be  evaluated
12600	without  further  search.   Attached to the endpoints on the diagrams
12700	are the values given to the corresponding positions.   These  numbers
12800	are  from  the  point  of  view  of  the  program;  large numbers are
12900	favorable for it.  If we assume that each side would  make  the  move
13000	that  is best for it in each of the positions just before the then of
13100	the tree, then we can assign values to these positions  as  shown  in
13200	brackets.  Continuing this process gives values to all the positions.
13300	
13400		All  present  chess  programs use these values, but the early
13500	programs looked at all the positions in order to get them.   However,
13600	if  the  program looks at positions from the top down in the diagram,
13700	it is clear that the positions marked in red need never be  examined.
13800	Thus,  after  the  positions  with  values  8,1,6,3,and  9  have been
13900	examined, it is clear that the minimizing player will  not  make  the
14000	move  to [9] since he can be sure of keeping the score to 8 by moving
14100	to [8] and will allow a score of at least 9 by moving to  [9].     To
14200	look  at  5  at  this  point  is  as  though  a  chess  player, after
14300	determining that a certain move wins a pawn, discovers  that  another
14400	move  allows  the  opponent  to  capture one of his rooks without any
14500	compensation, then examines other moves of the opponent.    The  move
14600	that  allows  the rook capture is already refuted; it is fruitless to
14700	look at what else the opponent might do, since it does not  influence
14800	our choice of move.
14900	
15000		Clearly,  the  alpha-beta  heuristic  saves  looking  at some
15100	positions, but we emphasize the following points:
15200	
15300		1. If moves are looked at in the right order (it is  best  to
15400	look at the best moves first), the number of positions looked at with
15500	alpha-beta  is  about  the  square  root  of  the  number  looked  at
15600	otherwise.  Thus, analysis involving 10,000 positions with alpha-beta
15700	may require looking at 100,000,000 without it.  The  difference  will
15800	allow  a  slow  computer  to beat a fast one or even allow a human to
15900	beat a computer.
16000	
16100		2. Alpha-beta is used without explicit thought by human  game
16200	players,  but  was  not  noticed by the first authors of game-playing
16300	programs.  This suggests that many of the algorithms required to make
16400	machines  behave  intelligently  can  be  found  by  observing  human
16500	behavior carefully, but this is more difficult than it might seem.
16600	
16700		3. One of the main methods of artificial intelligence  is  to
16800	make  a  program  that behaves the way we think humans do or at least
16900	ought to.  If the program is not as successful as humans, examination
17000	of its mistakes will sometimes turn up an aspect of human behavior we
17100	have missed, because we normally take it for granted.
17200	
17300		Here are some more aspects of  human  game-playing  behavior,
17400	some  of which have been incorporated into game-playing programs, but
17500	others still give us difficulties.
17600	
17700		1. We can often consider two moves occurring in two different
17800	positions as "the same move".  For example, they may both involve 
17900	moving the same piece from a given square to a given other square.
18000	In general, the "same move" will have different effects in different
18100	positions, but often the effects are the same or at least some of the
18200	important properties are the same.  Humans are rather good at noticing
18300	this so as to not repeat computations, but present computer programs
18400	do it to a very limited extent.
18500	
18600		2.